package leetcode;

//给定两个序列，求其中一个序列变换为另一个序列一共有多少种方法
public class DistinctSubSequence {

	public static void main(String[] args) {
		System.out.println(numDistinct("rabbbit", "rabbit"));
	}
	
	//典型的dp思想，假设两个序列的长度分别是i，j
	//如果最后一个元素相等，那么等于不要这个元素方法加上在原串中去掉最后一个之后的方法
	//比如“aaaabbcc” 与“aaac” 等于“aaaabbc” 与“aaa”  和“aaaabbc”与“aaac”的总和
	//dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]  (if S[i] == T[j]) i > 0 ,j>0 
	//当最后一个元素不相等的时候，只能是原串中删除最后一个元素
	//dp[i][j] = dp[i - 1][j]  (if S[i] != T[j])   i > 0
	
	//边界条件dp[0][0] = 1; dp[1][0] = 1(任何非空子串能变为空字符串)，dp[0][1] = 0(空子串不能变为非空字符串)
	public static int numDistinct(String S, String T) {
		if (S == null || T == null) {
			return -1;
		}
		if(T.length() <= 0 ){
			return 1;
		}
		if(S.length() <= 0 ){
			return 0;
		}
		int[][] result = new int[S.length() + 1][T.length() + 1];
		result[0][0] = 1;
		for (int i = 0; i < result.length; i++) {
			result[i][0] = 1;
		}
		result[0][1] = 0;
		for (int i = 1; i < result.length; i++) {
			for (int j = 1; j < result[0].length; j++) {
				if(S.charAt(i - 1) == T.charAt(j - 1)){
					result[i][j] = result[i - 1][j - 1] + result[i - 1][j];
				}else {
					result[i][j] = result[i - 1][j];
				}
			}
		}
		for (int[] a: result) {
			for (int i : a) {
				System.out.print(i+"  ");
			}
			System.out.println();
		}
		return result[S.length()][T.length()];
	}
}
